import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-22
 * Time: 23:15
 */
// class Solution {
//     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
//         List<List<Integer>> res = new ArrayList<>();
//         traversal(root, res, 0);
//         return res;
//     }

//     private void traversal(TreeNode root, List<List<Integer>> res, int level) {
//         if (root == null) {
//             return;
//         }

//         if (res.size() == level) {
//             res.add(new ArrayList<Integer>());
//         }

//         if ((level & 1) == 1){//如果是奇数层次就从右往左遍历
//             res.get(level).add(0, root.val);
//         } else {
//             res.get(level).add(root.val);
//         }

//         traversal(root.left, res, level + 1);
//         traversal(root.right, res, level + 1);
//     }
// }



// class Solution {
//     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
//         List<List<Integer>> result = new ArrayList<>();
//         if (root == null) {
//             return result;
//         }
//         Queue<TreeNode> queue = new LinkedList<>();
//         queue.add(root);
//         // 统计这一层的节点数
//         while (!queue.isEmpty()) {
//             // 该层的节点数量
//             int levelCount = queue.size();
//             ArrayList<Integer> sub = new ArrayList<>();
//             while (levelCount > 0) {
//                 TreeNode node = queue.poll();
//                 // 根据层次来判断顺序
//                 if (result.size() % 2 == 0) {//偶数层次就是从左往右就是正常的程序遍历
//                     sub.add(node.val);
//                 } else {//否则的话就是从右向左遍历
//                     sub.add(0, node.val);
//                 }

//                 if (node.left != null) {
//                     queue.add(node.left);
//                 }
//                 if (node.right != null) {
//                     queue.add(node.right);
//                 }
//                 levelCount--;
//             }
//             result.add(sub);
//         }
//         return result;
//     }
// }
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution4 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 统计这一层的节点数
        while (!queue.isEmpty()) {
            // 该层的节点数量
            int levelCount = queue.size();
            ArrayList<Integer> sub = new ArrayList<>();
            while (levelCount > 0) {
                TreeNode node = queue.poll();
                // 根据层次来判断顺序
                if (result.size() % 2 == 0) {
                    sub.add(node.val);
                } else {
                    sub.add(0, node.val);
                }

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                levelCount--;
            }
            result.add(sub);
        }
        return result;
    }
}


class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(root, res, 0);
        return res;
    }

    private void traversal(TreeNode root, List<List<Integer>> res, int level) {
        if (root == null) {
            return;
        }

        if (res.size() == level) {
            res.add(new ArrayList<Integer>());
        }

        if ((level & 1) == 1){
            res.get(level).add(0, root.val);
        } else {
            res.get(level).add(root.val);
        }

        traversal(root.left, res, level + 1);
        traversal(root.right, res, level + 1);
    }
}
public class TestDemo {

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.right = node5;
       solution.zigzagLevelOrder(node1);
    }

}
